#include "search.h"
#include <cstring>
#include <ctime>
#include <cstdlib>

const int Search::DIRX[4] = {1, 0, -1, 0};
const int Search::DIRY[4] = {0, -1, 0, 1};

Search::Search(int maxLevel) {
    mMaxLevel = maxLevel;
    eval = new Eval();
}

Search::~Search() {
    delete eval;
}

void Search::SetMaxLevel(int maxLevel) {
    unsigned seed = time(0);
    srand(seed);
    mMaxLevel = maxLevel;
    mColor = 0;
}

inline char lowbyte(int n) {
    return (char)(n & 0xFF);
}

Solution Search::SearchNextMove(int step, const Positions & positions) {
    /* 检查AI方的颜色 */
    mColor = -1;
    for (auto & it : positions) {
        if (lowbyte(it.first) == 'g' || lowbyte(it.first) == 'G') {
            mColor = (lowbyte(it.first) == 'G') ^ (it.second.y < 5) ^ 1;
            break;
        }
    }
    if (mColor == -1) {
        Solution ret;
        ret.from = (Coordinate){1, 7};
        ret.to = (Coordinate){4, 7};
        return ret;
    }

    static Board board;
    TransformToBoard(board, positions);
    auto res = CorrectMove(board, positions);

    return res.first;
}

bool Search::IsEnemy(int piece) const {
    return (lowbyte(piece) >= 'a') ^ mColor;
}

bool Search::InRange(int x, int y) const {
    return x >= 0 && x < 9 && y >= 0 && y < 10;
}

bool Search::InRange(const Coordinate & c) const {
    return InRange(c.x, c.y);
}

bool Search::TransformToBoard(Board board, const Positions & positions) {
    memset(board, 0, sizeof(Board));
    for (auto & it : positions) {
        board[it.second.x][it.second.y] = it.first;
    }
    return true;
}

std::vector<Coordinate> Search::GetMovable(const Board board, Coordinate c) {
    std::vector<Coordinate> ret;
    if (board[c.x][c.y] == 0 || IsEnemy(board[c.x][c.y])) {
        return ret;
    }
    char piece = lowbyte(board[c.x][c.y]);
    if (piece >= 'a') {
        piece = piece - 'a' + 'A';
    }
    int tx, ty;
    switch (piece) {
        case 'R': {
            for (int k = 0; k < 4; k++) {
                tx = c.x + DIRX[k];
                ty = c.y + DIRY[k];
                while (InRange(tx, ty)) {
                    if (board[tx][ty]) {
                        if (IsEnemy(board[tx][ty])) {
                            ret.push_back((Coordinate){tx, ty});
                        }
                        break;
                    }
                    ret.push_back((Coordinate){tx, ty});
                    tx += DIRX[k];
                    ty += DIRY[k];
                }
            }
            break;
        }
        case 'H': {
            for (int abs_dx = 1; abs_dx <= 2; abs_dx++) {
                int abs_dy = 3 - abs_dx;
                for (int s = -1; s <= 1; s += 2) {
                    tx = c.x + abs_dx * s;
                    for (int t = -1; t <= 1; t += 2) {
                        ty = c.y + abs_dy * t;
                        if (!InRange(tx, ty)) {
                            continue;
                        }
                        if (board[c.x + abs_dx / 2 * s][c.y + abs_dy / 2 * t]) {
                            continue;
                        }
                        if (board[tx][ty] && !IsEnemy(board[tx][ty])) {
                            continue;
                        }
                        ret.push_back((Coordinate){tx, ty});
                    }
                }
            }
            break;
        }
        case 'E': {
            for (int s = -1; s <= 1; s += 2) {
                tx = c.x + 2 * s;
                for (int t = -1; t <= 1; t += 2) {
                    ty = c.y + 2 * t;
                    if (!InRange(tx, ty) || ty < 5) {
                        continue;
                    }
                    if (board[c.x + s][c.y + t]) {
                        continue;
                    }
                    if (board[tx][ty] && !IsEnemy(board[tx][ty])) {
                        continue;
                    }
                    ret.push_back((Coordinate){tx, ty});
                }
            }
            break;
        }
        case 'A': {
            for (int s = -1; s <= 1; s += 2) {
                tx = c.x + s;
                if (tx < 3 || tx > 5) {
                    continue;
                }
                for (int t = -1; t <= 1; t += 2) {
                    ty = c.y + t;
                    if (ty < 7 || ty > 9) {
                        continue;
                    }
                    if (board[tx][ty] && !IsEnemy(board[tx][ty])) {
                        continue;
                    }
                    ret.push_back((Coordinate){tx, ty});
                }
            }
            break;
        }
        case 'G': {
            for (int k = 0; k < 4; k++) {
                tx = c.x + DIRX[k];
                ty = c.y + DIRY[k];
                if (tx < 3 || tx > 5 || ty < 7 || ty > 9) {
                    continue;
                }
                if (board[tx][ty] && !IsEnemy(board[tx][ty])) {
                    continue;
                }
                ret.push_back((Coordinate){tx, ty});
            }
            break;
        }
        case 'C': {
            for (int k = 0; k < 4; k++) {
                tx = c.x + DIRX[k];
                ty = c.y + DIRY[k];
                while (InRange(tx, ty) && board[tx][ty] == 0) {
                    ret.push_back((Coordinate){tx, ty});
                    tx += DIRX[k];
                    ty += DIRY[k];
                }
                do {
                    tx += DIRX[k];
                    ty += DIRY[k];
                } while (InRange(tx, ty) && board[tx][ty] == 0);
                if (InRange(tx, ty) && IsEnemy(board[tx][ty])) {
                    ret.push_back((Coordinate){tx, ty});
                }
            }
            break;
        }
        case 'S': {
            tx = c.x;
            ty = c.y - 1;
            if (InRange(tx, ty)) {
                if (board[tx][ty] == 0 || IsEnemy(board[tx][ty])) {
                    ret.push_back((Coordinate){tx, ty});
                }
            }
            if (c.y < 5) {
                ty = c.y;
                for (int dx = -1; dx <= 1; dx += 2) {
                    tx = c.x + dx;
                    if (!InRange(tx, ty)) {
                        continue;
                    }
                    if (board[tx][ty] && !IsEnemy(board[tx][ty])) {
                        continue;
                    }
                    ret.push_back((Coordinate){tx, ty});
                }
            }
            break;
        }
        default:
            break;
    }
    return ret;
}

std::vector<Solution> Search::GetAllMoves(const Board board, const Positions & positions) {
    std::vector<Solution> sols;
    for (auto it : positions) {
        auto possibilities = GetMovable(board, (Coordinate){it.second.x, it.second.y});
        for (const Coordinate & c : possibilities) {
            Solution tem;
            tem.from = (Coordinate){it.second.x, it.second.y};
            tem.to = (Coordinate){c.x, c.y};
            sols.push_back(tem);
        }
    }
    return sols;
}

std::pair<Solution, bool> Search::RandomMove(const Board board, const Positions & positions) {
    Solution sol;
    std::vector<std::vector<Coordinate> > all;
    std::vector<Coordinate> coors;
    for (auto it : positions) {
        auto possibilities = GetMovable(board, (Coordinate){it.second.x, it.second.y});
        if (possibilities.size() > 0) {
            coors.push_back((Coordinate){it.second.x, it.second.y});
            all.push_back(possibilities);
        }
    }
    if (all.size() == 0) {
        return std::make_pair(sol, false);
    }

    int idx = rand() % all.size();
    sol.from = coors[idx];
    const auto & possi = all[idx];
    sol.to = possi[rand() % possi.size()];
    return std::make_pair(sol, true);
}

static const int INF = 0x3c3c3c3c;

std::pair<Solution, bool> Search::CorrectMove(const Board board, const Positions & positions) {
    if (mMaxLevel < 1) {
        return RandomMove(board, positions);
    }
    Solution sol;
    std::vector<Solution> sols = GetAllMoves(board, positions);
    if (sols.size() == 0) {
        return std::make_pair(sol, false);
    }
    
    // 开始Alpha-Beta剪枝，sols里面存了所有可能的“边”
    int best = -INF;
    int alpha = -INF, beta = INF;
    static Board tBoard;
    memcpy(tBoard, board, sizeof(Board));
    Positions tPositions = positions;
    for (const Solution & s : sols) {
        int slayer = board[s.from.x][s.from.y];
        int victim = board[s.to.x][s.to.y];
        if (victim) {
            tPositions.erase(victim);
        }
        tPositions[slayer] = s.to;
        tBoard[s.to.x][s.to.y] = slayer;
        tBoard[s.from.x][s.from.y] = 0;

        int val = AlphaBeta(1, tBoard, tPositions, false, alpha, beta);
        if (best < val) {
            best = val;
            sol = s;
        }
        alpha = std::max(alpha, best);

        tBoard[s.from.x][s.from.y] = slayer;
        tBoard[s.to.x][s.to.y] = 0;
        tPositions[slayer] = s.from;
        if (victim) {
            tBoard[s.to.x][s.to.y] = victim;
            tPositions[victim] = s.to;
        }

        // pruning
        if (beta <= alpha) {
            break;
        }
    }

    return std::make_pair(sol, true);
}

int Search::AlphaBeta(int depth, Board board, Positions & positions, bool isMaximizer, int alpha, int beta) {
    if (depth == mMaxLevel) {
        return eval->Evaluate(board, positions) * (mColor == 0 ? 1 : -1);
    }

    std::vector<Solution> sols = GetAllMoves(board, positions);
    int best;
    if (isMaximizer) {
        best = -INF;
    }
    else {
        best = INF;
    }

    for (const Solution & s : sols) {
        int slayer = board[s.from.x][s.from.y];
        int victim = board[s.to.x][s.to.y];
        if (victim) {
            positions.erase(victim);
        }
        positions[slayer] = s.to;
        board[s.to.x][s.to.y] = slayer;
        board[s.from.x][s.from.y] = 0;

        int val = AlphaBeta(depth + 1, board, positions, !isMaximizer, alpha, beta);
        if (isMaximizer) {
            best = std::max(best, val);
            alpha = std::max(alpha, best);
        }
        else {
            best = std::min(best, val);
            beta = std::min(beta, best);
        }

        board[s.from.x][s.from.y] = slayer;
        board[s.to.x][s.to.y] = 0;
        positions[slayer] = s.from;
        if (victim) {
            board[s.to.x][s.to.y] = victim;
            positions[victim] = s.to;
        }

        // pruning
        if (beta <= alpha) {
            break;
        }
    }
    return best;
}
